A problem in computer graphics and computer imaging is rendering, which is the acquisition and processing of signals by a computer. A related problem in imaging is known as demosaicing, which is a digital process used to reconstruct a full color image from an incomplete signal output with missing color information such as from an image sensor. The problem of rendering is integral to computer graphics and computer imaging that it has been an active area of research for over 40 years.
Recently, there has been growing interest in using compressed sensing for various applications, but not to efficiently perform computer graphics and computer imaging. For purposes of this application, the term “image” as used herein may refer to a digital image or video stream with more than one signal—a multidimensional signal.
Multidimensional signals are often present in computer graphics and computer imaging. For example, an image includes spatial dimensions such that it is a 2-dimensional array of numbers defining a two-dimensional (“2-D”) signal whereas a time-varying video is a three-dimensional (“3-D”) signal because in addition to the spatial dimensions, there is a time dimension. In generating graphics or images for certain applications, the signal may have additional dimensions such as when performing Monte Carlo rendering. Monte Carlo rendering includes computational algorithms that rely on a series of random samples to compute results. For example, suppose there is a time varying scene that is being rendered with a camera with a finite aperture. In this case, the scene might describe a multidimensional function such as a five-dimensional (“5-D”) function ƒ(x, y, u, v, t) where (x, y) describes the position of the sample on the image plane, t is the time at which the sample is taken, and (u, v) is the position on the aperture for depth-of-field effects. Typically Monte Carlo rendering randomly samples the multidimensional function by picking random values for x, y, u, v, t and then evaluating the function. A 2-D image can be produced by integrating out certain dimensions. Typically, if only a small number of samples are taken, the resulting image is extremely noisy and unacceptable, because there are not enough samples to properly represent the signal. As more samples are taken, the resulting image converges to the theoretically-correct image slowly over time.
In the field of imaging, compressed sensing has been used to try to accelerate the acquisition of images. However, most of compressed sensing techniques in this field capture an image by taking projections of the image with a large set of different random patterns. Unfortunately, these methods require thousands of serial measurements in order to reconstruct a high-quality resolution image, which makes them impractical for most real-world imaging applications, because they are simply too slow.
In the field of rendering, it is well known that the final, rendered image can be efficiently compressed with a transform-coding compression algorithm, which implies that the information content of the image can be described more compactly than with its pixel representation.
Most systems, however, expend their effort in rendering every single pixel in the spatial domain of the image first, only to discard the redundant information during the post-process compression. Most rendered images are eventually compressed by some method of either static—JPEG or JPEG2000—or video—MPEG or MPEG4—image compression. Similar to capturing an image, it would be advantageous to exploit the sparsity in the transform domain directly during rendering so that only the important parts of the image are rendered, as opposed to rendering everything first and then throwing away most of the useless information.
This seems to imply that there might be a way to accelerate the rendering process directly in the transform domain. Unfortunately, the obvious approach of taking the transform of a signal is extremely difficult for anything other than extremely simple analytic scene representations. In addition, all of the known rendering algorithms to date such as ray tracing, REYES, and scanline algorithms fail to map to other transform domains.
In order to develop a framework that exploits sparsity in a transform domain, it has to be compatible with the traditional point-sampling methods common to all of these rendering algorithms. In the area of image rendering, transform compression techniques have been used primarily for accelerating the computation illumination. For example, an elegant hierarchical approach has been used to create a multi-resolution model of the radiosity in a scene. However, this approach does not explicitly use a wavelet basis, nor does it exploit the final image coherence.
Recently, interest in transform-domain techniques for illumination has been renewed with research into efficient pre-computed radiance transfer methods using bases such as spherical harmonics. Again, these approaches focus on using the sparsity of the illumination or the Bidirectional Reflectance Distribution Function (“BRDF”) in a transform domain, not on exploiting the sparsity of the final image.
In terms of using transform-domain approaches to synthesize the final image, the most successful work has been in the field of volume rendering. In this area, both the Fourier and wavelet domains have been leveraged to reduce rendering times. However, this approach does not map well to the problem of exploiting sparsity in the final image to accelerate standard image rendering.
Most of the work in accelerating ray tracing has focused on novel data structures for accelerating the scene traversal. However, there are algorithms to accelerate rendering that take advantage of the spatial correlation of the final image, which in the end is related to the sparsity in the wavelet domain. Most common is the process of adaptive sampling in which a fraction of the samples are computed and new samples are computed only where the difference between measured samples is large enough such as by a measure of contrast. These adaptive sampling methods still compute the image in the spatial domain making it impossible to apply arbitrary wavelet transforms.
Although there are sampling/reconstruction techniques for improving rendering to generate better quality images in shorter times than with standard techniques, these techniques focus on sampling the multidimensional scene information efficiently instead of focusing on reconstructing the image efficiently in a transform domain.
Furthermore, many times in rendering one must compute the definite integral of an unknown function. Other algorithms must solve the integral of a signal that is known but difficult to describe in analytic form suitable for integration. This problem is encountered in a variety of application areas such as algorithms that compute the illumination in a scene, algorithms that determine the reflection off a surface with a complex BRDF, or even algorithms that synthesize images by calculating image effects such as depth-of-field or motion blur for image synthesis.
The most common approach for solving these integrals in computer graphics is known as “Monte Carlo” integration, where a large number of random point samples of the function are taken and used to estimate the value of the integral with some probability. As more samples are taken, the variance of the result is reduced and the integral is estimated more accurately. Theoretically, an infinite number of samples are needed to get an exact estimate of the value of the integral. In practice, it is well known that these methods require many samples to converge, and as a result consume most of the computation time in the algorithms.
Another problem in computer graphics occurs when generating a discrete image of a continuous scene representation, known as antialiasing. One approach specifies that a signal must be sampled at more than twice its highest frequency, otherwise known as the Nyquist rate, in order to be reconstructed accurately. The continuous scene can have sharp boundaries, which means that theoretically the signal has infinite bandwidth and would therefore require an infinite number of samples for reconstruction. Therefore, if the signal is sampled at a rate lower than the Nyquist rate, aliasing will occur where high frequency content not captured by the sampling rate appears as lower frequency content. In rendering, aliasing in the image appears as the “jaggies” along sharp boundaries in the scene.
Antialiasing algorithms attempt to band limit the signal so that the frequency of the signal will be within the Nyquist rate before being sampled. Theoretically, this can be done by the convolution with a sinc( ) function in the spatial domain (multiplication by a rect( ) function in the frequency domain), but in practice other approaches are typically used since the sinc( ) is not a localized filter. One common approach is to use a box filter in pixel space, which effectively integrates the signal under a pixel in order to antialias it. These integrals are typically computed from a few fixed samples in the case of real-time rasterization hardware, or from many random samples in the case of high-end rendering systems.
There is a need for a system and methods that provides an improved approximation of an original signal that provides better results, including the generation of graphics or images with little or no distortion artifacts or motion blur. The present invention satisfies this demand.